﻿// 1-12_0.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
//检1
int countOnes(int n) {  //统计整数二进制展开中位数1的总数：O(logn)
    int ones = 0;  //计数器复位
    while (0 < n) {  //在n缩减至0之前，反复地
        ones += (1 & n);  //检查最低位，若为1则记数
        n >>= 1;  //右移一位
    }
    return ones;  //返回计数
}
//消1
//复杂度正比于目标数1的个数
int countOnesA(int n) {
    int ones = 0;  //计数器
    while (0 < n) {  //在n缩减至0之前，反复地
        ones++;
        n &= n - 1;  //即 n = n & (n-1)；整个的灵魂所在，利用n的二进制、n-1的二进制，二者结构上的特殊性，以及位与运算
    }
    return ones;
}

//暂放
//复杂度loglogn（基本等同常数了）
int countOnesB(int n) {
    int ones = 0;
    return ones;
}
int main()
{
    int a = countOnes(441);
    int b = countOnesA(441);
    std::cout << a <<"\n";
    std::cout << b <<"\n";
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
